User talk:Ikosarakt1/Extension of traditional notations for non-recursive ordinals
You haven't said what does \(\theta_1(\Omega)\) actually mean. I guess this is limit of ordinals otherwise unaccesible by \(\theta_1(\alpha)\) for \(\alpha\) countable. Is that right? LittlePeng9 (talk) 15:52, April 24, 2013 (UTC) Roughly speaking, it is \(\theta_1(\theta_1(\theta_1(\cdots)))\) (with \(\omega\) \(\theta_1\)'s). It is by analogy with normal \(\theta\) function. Ikosarakt1 (talk ^ ) 16:01, April 24, 2013 (UTC) Ah, I see. But I must admit I hate sort of things you just did - \(\theta_1(\theta_1(\theta_1(\cdots(\theta_1(1))\cdots)))\) cannot be stack \(\omega\) long, because \(\omega\), by definition, has no last element. What you just did would be \(\omega+1\). I'm being picky right now, but it annoys me a bit when people forgot how limit ordinals work. LittlePeng9 (talk) 16:05, April 24, 2013 (UTC) Thanks for correction. By the way, you working at some extremely fast-growing function, can you tell me what's the order type of that function? Ikosarakt1 (talk ^ ) 16:13, April 24, 2013 (UTC) As for now, it reaches as far as Goucher's ordinal. But I'm planning on getting above it. LittlePeng9 (talk) 16:23, April 24, 2013 (UTC) About your notation - how about adding 4th variable \(\delta\), such that for \(\delta=1\) we get theta functions, for \(\delta=2\) we get lambda function, for \(\delta=3\) we get... You don't have letter for that. And that's a point! You don't need one! LittlePeng9 (talk) 16:39, April 24, 2013 (UTC) It is obvious, I thought about it earlier. I just didn't have time to add this. Yes, we can add more variables, up to applying transfinite ordinals again and again. Ikosarakt1 (talk ^ ) 18:10, April 24, 2013 (UTC) "Recursive extension" of \(\theta_1(\alpha)\) I also had the idea of considering all recursive extensions of \(\theta_1(\alpha) = \omega_{\alpha}^{\text{CK}}\), but it leads to the following question: how exactly do you rigorously define what a "recursive extension" of \( \omega_{\alpha}^{\text{CK}}\) is? For the recursive ordinals, we know how to define recursive functions by Turing machines, and from there we can define recursive sets, recursive relations, recursive partial orders, and therefore recursive ordinals. But here, we have \( \omega_{\alpha}^{\text{CK}}\), which is not recursive, so is not defined by any Turing machine. Obviously, what we want is some notion of "any algorithm involving the function \(\theta_1(\alpha) = \omega_{\alpha}^{\text{CK}}\)", but how do we define "any algorithm" here? It's an interesting puzzle. Deedlit11 (talk) 05:29, May 9, 2013 (UTC) :\(\theta_1(\alpha)\) is much larger ordinal than \(\omega_\alpha^\text{CK}\), which is actually \(\theta_1(0,\alpha)\). :If we able to define \(\theta_1(0,1) = \omega_1^\text{CK}\), we can notice that every term of its fundamental sequence can be defined using \(\theta(\alpha)\). The corresponding term of FS for \(\theta_2(0,1)\) will be analogical expect that \(\theta(\alpha)\) replaced by \(\theta_1(\alpha)\). If \(\theta_1(0,1)n = \theta(\Omega)\), then \(\theta_2(0,1)n = \theta_1(\Omega)\). I believe it works correctly. Ikosarakt1 (talk ^ ) 09:53, May 9, 2013 (UTC) ::In the first sentence, you meant \( \), right? FB100Z • talk • 17:57, May 10, 2013 (UTC) ::Yes. Thanks, improves. Ikosarakt1 (talk ^ ) 18:02, May 10, 2013 (UTC) ::What? You cannot define every term in the fundamental sequence of \(\omega_1^\text{CK}\) using \(\theta(\alpha)\), or any recursive notation at all for that matter. By the very definition of \(\omega_1^\text{CK}\), every recursive notation must end below it. The only way to get to \(\omega_1^\text{CK}\) is to utilize Turing machines or some other Turing-complete system. To define a fundamental sequence for \(\theta_2(0,1)\), we would need to utilize a similar system that describes all "recursive extensions" of \(\theta_1(\alpha)\), and for that we need a precise definition. Deedlit11 (talk) 00:19, May 11, 2013 (UTC) Variant of Kleene's O Let \(K\) be the set of all notations, let \(<_\mathcal{O}\) be an operator indicating a well-ordering of \(K\), and let \(\mathcal{O}_1\) be a function mapping notations to ordinals. * \(0 \in K\) and \(\mathcal{O}_1(0) = 0\). * If \(n \in K\) and \(\mathcal{O}_1(n) = \alpha\), then \(2^n \in K\), \(\mathcal{O}_1(2^n) = \alpha + 1\), and \(n <_\mathcal{O} 2^n\). * If \(n \in K\), \(n \neq 0\), and \(\mathcal{O}_1(n) = \alpha\), then \(7^n \in K\), \(\mathcal{O}_1(7^n) = \omega^\text{CK}_\alpha\), and \(n <_\mathcal{O} 7^n\). * If for all natural numbers \(n\), we have \(f_i(n) \in K\) and \(f_i(n) <_\mathcal{O} f_i(n + 1)\), then \(3 \cdot 5^i \in K\), \(\mathcal{O}_1(3 \cdot 5^i) = \lim_{k \rightarrow \omega} \mathcal{O}_1(f_i(k))\), and for all \(k\) \(f_i(k) <_\mathcal{O} 3 \cdot 5^i\). * \(a <_\mathcal{O} b\) and \(b <_\mathcal{O} c\) implies \(a <_\mathcal{O} c\). How far does this get us? FB100Z • talk • 05:53, May 9, 2013 (UTC) :*bump* FB100Z • talk • 23:25, May 13, 2013 (UTC) ::But if we let \(n=\omega_1^\text{CK}\), then \(n<_\mathcal{O}7^n\), thus \(\mathcal{O}_1(n)=1\varphi^\text{CK}0\), using \(\varphi^\text{CK}\) as an operator. 10:26, December 26, 2017 (UTC) :::We can't let \(n=\omega_1^\text{CK}\), since \(n\) is restricted to natural numbers. LittlePeng9 (talk) 10:28, December 26, 2017 (UTC) Can you please explain what these formulas mean? Ikosarakt1 (talk ^ ) 17:08, May 14, 2013 (UTC) :This is just a copy of Kleene's O with another rule added; namely it gives the recursive functions access to the function \(\alpha \mapsto \omega_\alpha^\text{CK}\). FB100Z • talk • 07:12, May 15, 2013 (UTC) As far as I know, this and many other such notations hit problem when it comes to large nonrecursive ordinals if they aren't given oracle. For example, it is impossible to reach \(\omega^{CK}_1\cdot 2\) without oracle, unless your function numbering extends outside recursive functions. LittlePeng9 (talk) 18:23, May 14, 2013 (UTC) : how are \(K\) and \(f_i\) defined? We need \(f_i\) to be more than just recursive functions to extend beyond \(\omega_1^{\text{CK}}\). Deedlit11 (talk) 23:07, May 14, 2013 (UTC) :: \(K\) is the set of notations and \(f_i\) is \(i\)th partial recursive function. Everything except the line highlighted in green is identical to the original Kleene's O. FB100Z • talk • 07:12, May 15, 2013 (UTC) : @LittlePeng Now that you mention that, I realize that this notation is kind of a dead end. It's like taking a pistol (Kleene's O with no oracles) and loading it with an atomic bomb (\(\alpha \mapsto \omega_\alpha^\text{CK}\)). I don't think my system can reach \(\omega^{CK}_1 \cdot 2\), but it does have access to \(\omega_2^{CK} = \mathcal{O}_1(7)\), \(\omega_3^{CK} = \mathcal{O}_1(7^2)\), \(\omega_2^{CK} = \mathcal{O}_1(7^{2^2})\), etc. Since \(f(n) = 7^{^2n}\) is a computable function, \(\omega_\omega^\text{CK}\) also has a notation. FB100Z • talk • 07:12, May 15, 2013 (UTC) : \(\mathbb{O}_1\) isn't notation above \(\omega^\text{CK}_1\cdot 2\) because it lacks almost all ordinals. One simple example is that we can't define fundamental sequence for \(\omega^\text{CK}_2\). However, supremum of ordinals definable in that system is quite harder problem; we can define ordinals at least up to Goucher's ordinal, and we can also define that one, so it goes quite far. LittlePeng9 (talk) 12:32, May 15, 2013 (UTC) :: I am curious about the following questions: :: a) how far does \(\mathcal{O}_1\) go? :: b) how can we fill in its gaps? FB100Z • talk • 19:19, May 17, 2013 (UTC) :::I'm pretty sure we need to use some notion of oracle Turing machines to fill in the gaps. Deedlit11 (talk) 23:53, May 17, 2013 (UTC) ::::well yeah. ::::you defined level-\(\alpha\) Turing machines for countable \(\alpha\). maybe that will help us? FB100Z • talk • 00:05, May 18, 2013 (UTC) :::::Yes, I believe so. Of course, we need to modify the notation so that its specifies which oracle Turing machine is being used, but other than that it should work. Deedlit11 (talk) 23:54, May 18, 2013 (UTC) I've read many times about "magic" oracle solving halting problem, but the exact details of OTM haven't been shown, preventing us to evaluate even \(\Sigma_2(1)\). Ikosarakt1 (talk ^ ) 13:23, August 21, 2013 (UTC) : Here is definition I like: let us have standard machine with binary oracle tape with a property that \(n\)th cell has 1 written iff there is number \(m\) such that \(S(m)=n\). This allows us to easily check halting problem by simulating machine directly, and doesn't require any arbitrary numbering to choose. Most oracle machines work like this: let content of one-sided worktape be number n written in binary. Then machine entering special state O enters state Y if nth machine halts in some predetermined TM numbering halts, and enters state N otherwise. LittlePeng9 (talk) 16:38, August 21, 2013 (UTC) Aarex's Extension We have \(\omega^{CK}_{CK}\) = \(\omega^{CK}_{1,2}\), \(\omega^{CK}_{CK2}\) = \(\omega^{CK}_{1,3}\), etc. In general, \(\omega^{CK}_{...+CK^3k+CK^2l+CKm+n}\) = \(\omega^{CK}_{n,m+1,l+1,k+1,...}\). Next is ordinals using \(CK^\alpha\), \(\omega^{CK}_{CK^\alpha}\) = \(\omega^{CK}_{1,1...1,1,2}\) (\(\alpha\) 1's). The recursive \(CK^\alpha\) is \(\varepsilon_{CK+1}\)!AarexTiao 00:05, August 21, 2013 (UTC) What you done with Church and Kleene? You took the epsilon number of them! Ikosarakt1 (talk ^ ) 16:30, August 21, 2013 (UTC) :Church = C, Kleene = K and Chruch and Kleene = CK. Limit of Limit of ... Limit of Limit of recursive CK\(\alpha\)+1 = CK\(\alpha\)+1. What is Recursive limit of \(\alpha \rightarrow CK_\alpha\)? AarexTiao 23:36, August 21, 2013 (UTC) ::Let me explain - you broke up name of this ordinals in two parts, then you made statement about recursive CK's, whatever they are (it would be true for admissible ordinals, but they aren't recursive), then asked about recursive limit of ordinal function, without giving any basis for definition of it. Am I right? LittlePeng9 (talk) 06:36, August 22, 2013 (UTC) I made a similar notation. It starts like this: Make a version of Veblen's phi function called φCK. It works like the original Veblen hierarchy but the base is φCK(0,α) = ωαCK. It can be extended to multiple arguments like the original Veblen function. Then I made a version of the ψ function defined here. I made a new version of it called ψCK. It is defined as: ψCK(α) is the smallest ordinal not in the set which contains 0, 1, ω, Ω, and all ordinals definable from them using all recursive ordinal notations, and the ψCK function itself. 15:28, July 26, 2015 (UTC) : What do you mean by "definable from them using recursive ordinal notations"? By definition, recursive notations can only describe ordinals below \(\omega_1^\text{CK}\). You'd need to specify what you mean with "definable from them". LittlePeng9 (talk) 15:36, July 26, 2015 (UTC) : Use this version of psi: : \psi(\alpha) = \varepsilon_{\alpha} : \psi(\#\Omega) = \sup(\psi(\#),\psi(\#\psi(\#)),\psi(\#\psi(\#\psi(\#))),...) # is any valid expression. : In rule 2, it's not multiplication. It's plugging the ordinal to the current expression. : -- From the googol and beyond -- 20:30, July 26, 2015 (UTC)